package LeetCode;

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Solution {

	public static void main(String[] args) {
		ListNode l1 = new ListNode(9);
		ListNode l2 = new ListNode(1);
		// System.err.println(l1.val);
		// System.err.println(l2.val);
		ListNode r1 = l1;
		ListNode r2 = l2;
		/*
		 * int i = 2; while (i != 0) { ListNode p = new ListNode(2 + i); r1.next = p; r1
		 * = p; i--;
		 * 
		 * }
		 */
		int i = 9;

		while (i > 0) {
			ListNode p = new ListNode(9);
			r2.next = p;
			r2 = p;
			i--;

		}
		ListNode r = addTwoNumbers(l1, l2);
		while (r != null) {
			System.err.print(r.val);
			r = r.next;
		}

	}

	// 暴力穷举法
	public static int[] twoSum1(int[] nums, int target) {
		int len = nums.length;

		for (int i = 0; i < len; i++) {
			for (int j = i + 1; j < len; j++) {
				if (nums[i] + nums[j] == target) {

					return new int[] { i, j };
				}
			}
		}
		throw new IllegalArgumentException("No two sum solution");

	}

	// 哈希法
	public static int[] twoSum2(int[] nums, int target) {

		Map<Integer, Integer> map = new HashMap<Integer, Integer>();
		for (int i = 0; i < nums.length; i++) {
			map.put(nums[i], i);
		}
		for (int i = 0; i < nums.length; i++) {
			int complement = target - nums[i];
			if (map.containsKey(complement) && map.get(complement) != i) {
				return new int[] { i, map.get(complement) };
			}

		}
		throw new IllegalArgumentException("No two sum solution");

	}

	public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
		String num1 = "";
		String num2 = "";
		ListNode p1 = l1, p2 = l2;
		while (p1 != null) {
			num1 = num1 + Integer.toString(p1.val);
			p1 = p1.next;
		}
		while (p2 != null) {
			num2 = num2 + Integer.toString(p2.val);
			p2 = p2.next;
		}
		num1 = new StringBuffer(num1).reverse().toString();
		num2 = new StringBuffer(num2).reverse().toString();
		BigInteger n1 = new BigInteger(num1);
		BigInteger n2 = new BigInteger(num2);
		BigInteger sum = n1.add(n2);

		ListNode h = null, r = null;
		String rs = new StringBuffer(sum.toString()).reverse().toString();
		//int r1 = Integer.parseInt(rs); 越界异常
		if (rs.equals("0")) {
			ListNode t = new ListNode(0);
			t.next = null;
			return t;
		}
		int len = rs.length();
		int i = 0;
		while (!rs.equals("0") && i < len) {
			ListNode p = new ListNode(Integer.parseInt((String.valueOf(rs.charAt(i)))));
			if(h==null) {
				h=r=p;
			}else {
				r.next=p;
				r=p;
			}
			i++;
		}
		return h;
	}

}
